package com.lagou.impl;

import java.util.HashMap;
import java.util.Map;

public class Main {

    /**
     * 判断数组中得数字是不是唯一得
     *
     * @param array 数组
     * @return 返回是否唯一
     */
    public static boolean isUniqueNumber(int[] array) {
        Map<Integer, Integer> map = new HashMap<>(array.length);
        for (int value : array) {
            if (map.containsKey(value)) {
                return false;
            }
            map.put(value, map.getOrDefault(value, 0) + 1);
        }
        return true;
    }

    /**
     * 获取金矿最大收益  递归
     *
     * @param w 工人数量
     * @param n 金矿数量
     * @param p 金矿需要工人得数量
     * @param g 金矿的价值
     * @return 返回最优结果
     */
    public static int getBestGoldMining(int w, int n, int[] p, int[] g) {
        if (w == 0 || n == 0) {
            return 0;
        }
        // 如果剩余的工人,不足以挖剩下的金矿, 则最有收益跟上一轮一样
        if (w < p[n - 1]) {
            return getBestGoldMining(w, n - 1, p, g);
        }

        return Math.max(getBestGoldMining(w, n - 1, p, g), getBestGoldMining(w - p[n - 1], n - 1, p, g) + g[n - 1]);
    }

    /**
     * 获取金矿最大收益  dp
     *
     * @param w 工人数量
     * @param p 金矿需要工人得数量
     * @param g 金矿的价值
     * @return 返回最优结果
     */
    public static int getBestGoldMiningV2(int w, int[] p, int[] g) {
        int[][] dp = new int[g.length + 1][w + 1];
        for (int i = 1; i <= g.length; i++) {
            for (int j = 1; j <= w; j++) {
                // 如果剩余的工人,不足以挖剩下的金矿, 则最有收益跟上一轮一样
                if (j < p[i - 1]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - p[i - 1]] + g[i - 1]);
                }
            }
        }
        return dp[g.length][w];
    }

    public static void main(String[] args) {
        int[] array2 = new int[]{1, 2, 3};
        int[] array = new int[]{1, 2, 1};
        System.out.println(isUniqueNumber(array2));
        System.out.println(isUniqueNumber(array));


        int w = 10;
        int[] p = {5, 5, 3, 4, 3};
        int[] g = {400, 500, 200, 300, 350};
        System.out.println(getBestGoldMining(w, g.length, p, g));
        System.out.println(getBestGoldMiningV2(w, p, g));
    }
}
